package leetcode; /**
 * description:
 * author:zt
 * date:2021-09-20
 */

import java.util.ArrayList;

/**
 * 给定一个单词数组和一个长度maxWidth，重新排版单词，使其成为每行恰好有maxWidth个字符，且左右两端对齐的文本。
 *
 * 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格' '填充，使得每行恰好有 maxWidth个字符。
 *
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 *
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 *
 * 说明:
 *
 * 单词是指由非空格字符组成的字符序列。
 * 每个单词的长度大于 0，小于等于maxWidth。
 * 输入单词数组 words至少包含一个单词。
 */
public class leetcode68 {
    public ArrayList<String> justifyFill (String[] words, int M) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        int n = words.length;
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < n; ) {
            list.clear();
            list.add(words[i]);
            int cur = words[i++].length();  //当前长度
            while (i < n && cur+1+words[i].length() <= M){
                cur += 1+words[i].length(); //注意空格
                list.add(words[i++]);
            }
            //只有一个单词
            if (list.size()==1){
                String s = list.get(0);
                while (s.length() != M) s += " ";
                res.add(s);
                continue;
            }

            if (i==n){
                StringBuilder sb = new StringBuilder(list.get(0));
                for (int j = 1; j < list.size(); j++) {
                    sb.append(" ").append(list.get(j));
                }
                while (sb.length() < M) sb.append(" ");
                res.add(sb.toString());
                break;
            }

            int wordLen = cur - (list.size()-1); //长度-空格个数
            int spaceLen = M - wordLen; //所需空格长度
            int sinSpaceLen = spaceLen / (list.size()-1); //单个空格长度
            String space = "";
            for (int j = 0; j < sinSpaceLen; j++) {
                space += " ";
            }
            StringBuilder sb = new StringBuilder();
            int sum = 0; //统计长度
            for (int j = 0; j < list.size(); j++) {
                String s = list.get(j);
                sb.append(s);
                if (j==list.size()-1) break;
                sb.append(space);
                sum += sinSpaceLen;
                int remain = list.size()-(j+1)-1; //剩余空格数量
                if (remain * sinSpaceLen + sum < spaceLen) {
                    sb.append(" ");
                    sum ++;
                }
            }
            res.add(sb.toString());
        }
        return res;
    }
}
